package com.kevinkk.tree;

import java.util.ArrayList;
import java.util.List;

/**
 * 给你二叉树的根节点 root 和一个整数目标和 targetSum ，找出所有 从根节点到叶子节点 路径总和等于给定目标和的路径。
 *
 * 叶子节点 是指没有子节点的节点。
 */

public class PathSumII {
    class Solution {
        List<List<Integer>> res = new ArrayList<>();

        public List<List<Integer>> pathSum(TreeNode root, int targetSum) {
            if(root == null) return res;
            traversal(root, targetSum, new ArrayList<Integer>());
            return res;
        }

        private void traversal(TreeNode node, int targetSum, List<Integer> list){
            list.add(node.val);
            if(node.left == null && node.right == null){
                int sum = 0;
                for(int i : list) sum += i;
                if(sum == targetSum) {
                    // 需要注意的是，当添加结果时，需要重新 new 一个 list 放入 res
                    // 否则后续其他路径对 list 进行修改时候，会破坏已经存入 res 的 list
                    res.add(new ArrayList<>(list));
                }
            }

            if(node.left != null){
                traversal(node.left, targetSum, list);
                list.remove(list.size()-1);
            }
            if(node.right != null){
                traversal(node.right, targetSum, list);
                list.remove(list.size()-1);
            }
        }
    }
}
